package java0514;

import java.util.*;

public class Bonus {
    public static int getMost(int[][] board) {
        // write code here
        int[][] price = new int[6][6];
        int max = 0;
        for (int i = 1; i < 6; i++) {
            price[0][i] = board[0][i] + price[0][i - 1];
        }
        for (int i = 1; i < 6; i++) {
            price[i][0] = board[i][0] + price[i - 1][0];
        }
        for (int i = 1; i < 6; i++) {
            for (int j = 1; j < 6; j++) {
                price[i][j] = (price[i - 1][j] > price[i][j - 1] ? price[i - 1][j] : price[i][j - 1]) +
                        board[i][j];
            }
        }
        return price[5][5];
    }

    public static void main(String[] args) {
        int[][] a = {
                {0, 1, 1, 1, 1, 1},
                {1, 1, 4, 1, 1, 1},
                {1, 1, 9, 1, 1, 1},
                {1, 1, 1, 3, 1, 1},
                {1, 1, 1, 1, 2, 1},
                {1, 1, 1, 1, 1, 1},
        };
        System.out.println(getMost(a));
    }
}
